///**
// *
// */
//package niuke;
//
//import java.util.ArrayList;
//import java.util.HashMap;
//import java.util.Scanner;
//import java.util.Stack;
//
///**
// * @author zhongfang
// *
// */
//public class 锟筋长锟斤拷锟斤拷 {
//
//	private static class TreeNode{
//		int val;
//		int index;
//		ArrayList<TreeNode> neibors=new ArrayList<>();
//		TreeNode parent;
//
//		public TreeNode(int x) {
//			index=x;
//		}
//	}
//	/**
//	 * @param args
//	 */
//	public static void main(String[] args) {
//		// TODO Auto-generated method stub
//		Scanner scanner=new Scanner(System.in);
//		int n=scanner.nextInt();
//		HashMap<Integer, TreeNode> nodes=new HashMap<>(n); //锟斤拷锟叫节碉拷
//		for (int i = 0; i < n-1; i++) {
//			int x=scanner.nextInt();
//			int y=scanner.nextInt();
//			TreeNode xNode,yNode;
//			if(nodes.containsKey(x)){
//				xNode=nodes.get(x);
//			}else {
//				xNode=new TreeNode(x);
//				nodes.put(x, xNode);
//			}
//			if(nodes.containsKey(y)){
//				yNode=nodes.get(y);
//			}else {
//				yNode=new TreeNode(y);
//				nodes.put(y, yNode);
//			}
//			xNode.neibors.add(yNode);
//			yNode.neibors.add(xNode);
//		}
//		for (int i = 1; i <= n; i++) {
//			nodes.get(i).val=scanner.nextInt();
//		}
//		generateTree(nodes);
//		//锟斤拷缺锟斤拷锟�
//		ArrayList<int[]> gcdLen=new ArrayList<>();
////		int curIndex=-1;
//		ArrayList<Integer> curPathIndexs=new ArrayList<>();
//		getResult(nodes.get(1),0,gcdLen,curIndex);
//	}
//
//
//	private static void getResult(TreeNode treeNode, int curGcd,ArrayList<int[]> gcdLen,ArrayList<Integer> curPathIndexs) {
//		if(treeNode.neibors.size()==1){//叶锟节碉拷
//
//		}
//		if(curPathIndexs.size()==0){//锟斤拷一锟斤拷锟节碉拷
//			int[] x={treeNode.val,1};
//			gcdLen.add(x);
//			curPathIndexs.add(0);
//		}
////		for (Integer curIndex : curPathIndexs) {
//		for(int curIndex=0;curIndex<gcdLen.size();curIndex++){
//			if(treeNode.val%curGcd==0){
//				gcdLen.get(curIndex)[1]=gcdLen.get(curIndex)[1]+1;
//			}else {
//				int maxGCD=getGCD(gcdLen.get(curIndex)[0],treeNode.val);
//				if(maxGCD==1){
//					int[] x={treeNode.val,1};
//					gcdLen.add(x);
//				}else {
//					int[] x={maxGCD,gcdLen.get(curIndex)[1]+1};
//					gcdLen.add(x);
//				}
//			}
//		}
//
//	}
//
//
//	private static int getGCD(int i, int j) {
//		int k;
//        while ((k=i%j) != 0) {
//            i = j;
//            j = k;
//        }
//        return j;
//	}
//
//
//	private static void generateTree(HashMap<Integer, TreeNode> nodes) {
//		Stack<TreeNode> stack=new Stack<>();
//		stack.add(nodes.get(1));
//		while (!stack.isEmpty()) {
//			TreeNode curNode=stack.pop();
//			for (TreeNode treeNode : curNode.neibors) {
//				if(treeNode.parent==null)
//					treeNode.parent=curNode;
//				treeNode.neibors.remove(curNode);
//				stack.add(treeNode);
//			}
//		}
//	}
//
//}
